package com.czh.problem.jianzhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指offer解题
 *
 * @author chenzhihua
 * @Date 2024/2/26
 */
public class SolutionOffer {
    public static void main(String[] args) {
        // 0,1,1,5,55,1134903170
        System.out.println(Fibonacci(0));
        System.out.println(Fibonacci(1));
        System.out.println(Fibonacci(2));
        System.out.println(Fibonacci(5));
        System.out.println(Fibonacci(10));
        System.out.println(Fibonacci(45));
    }

    /**
     * JZ10 斐波那契数
     */
    private static Map<Integer, Integer> map = new HashMap<>();

    public static int Fibonacci(int n) {
        //1.递归实现
//        if (n == 0 || n == 1) {
//            return n;
//        }
//        return Fibonacci(n - 1) + Fibonacci(n - 2);
        //2.hash+递归实现
//        if (n == 0 || n == 1) {
//            return n;
//        }
//        if (map.get(n) != null) {
//            return map.get(n);
//        } else {
//            int result = Fibonacci(n - 1) + Fibonacci(n - 2);
//            map.put(n, result);
//            return result;
//        }
        //3.动态规划实现
        if (n == 0 || n == 1) {
            return n;
        }
        int result = 0;
        int prepre = 0;
        int pre = 1;
        for (int i = 2; i <= n; i++) {
            result = prepre + pre;
            prepre = pre;
            pre = result;
        }
        return result;
    }



}
